import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class Test22 {
    public List<String> generateParenthesis(int n) {
        List<String> ret = new ArrayList<>();
        dfs(ret,"",n,n);
        return ret;
    }
    public void dfs(List<String> ret,String s,int left,int right){
        if (left == 0 && right == 0){
            ret.add(s);
            return;
        }
        if (left > right) return;// 剪枝
        if (left > 0) dfs(ret,s+"(",left-1,right);
        if (right > 0) dfs(ret,s+")",left,right-1);
    }
}
